The invention relates to transform processors, and more specifically, to real time discrete sinusoidal transform processors.
Discrete sinusoidal transforms play significant roles in various digital signal processing applications, such as spectrum analysis, image and speech signal processing, computer tomography, data compression, and signal reconstruction. Among different discrete sinusoidal transforms, the discrete cosine transform (DCT), the discrete sine transform (DST), discrete Hartley transform (DHT), and the discrete Fourier transform (DFT), are widely used because of their efficient performance. Recently, the Lapped Orthogonal Transform (LOT) and the Complex Lapped Transform (CLT) were introduced for transform coding with significantly reduced blocking effects and for motion estimation.
In the prior art, various special purpose computers and processor chips have been designed to accommodate specific operations. The algorithms specific to various transforms were implemented in hardware only designed to accommodate the handful of related algorithm transforms. This provided a simple solution to each transform problem, yet did not address the collective problem of solving a family of transforms. Examples of these include U.S. Pat. Nos. 4,760,543 (Ligtenberg et al.), 4,797,847 (Dunhamel), 4,679,163 (Arnould et al.), 4,831,574 (Dunhamel), 4,385,363 (Widergren et al.), 4,831,440 (Borgers et al.), 4,881,192 (Woudsma et al.), 4,791,598 (Liou et al.), 4,288,858 (Merola et al.), 4,674,125 (Carlson et al.), 4,849,922 (Riolfo), 5,053,985 (Friedlander et al.), and 4,449,194 (Wilhelm).
Various "fast" algorithms have been proposed in the past. Some of the more well-known in the art are disclosed in the following articles:
"A fast recursive algorithm . . . " published in the IEEE Transactions: Acoustic, Speech, Signal Processing, Vol. ASSP-35 on pages 1455-1461 in October 1987 and authored by H. S. Hou;
"A fast computational algorithm for the discrete cosine transform" published in the IEEE Transactions: Communication, vol. COM-25 on pages 1004-1009 in September 1977 and authored by W. H. Chen, C. H. Smith and S. C. Fralick;
"A new algorithm to compute the discrete cosine transform" published in the IEEE Transactions: Acoustics, Speech, Signal Processing, vol. ASSP-32 on pages 1243-1245 in December 1984 and authored by B. G. Lee.
Though these fast transforms have been implemented in hardware, the efficiency is reduced by architectural implementation and design constraints. Some factors retarding their functionality are large numbers of multipliers, latency and limitation on transform size N.
The prior art devices do not simultaneously produce both DCT and DST signals. In the past to provide DCT and DST a transposition was required. A single design for a transform processor wherein implementation in either lattice structure or infinite impulse response (IIR) filter structure has yet to be proposed. In past designs, the interconnections were global, not local, for optimal VLSI design. The past architectures have some limitations to the number of N-point data. The time-recursive nature of discrete sinusoidal transforms (DXT) was not used in the design and implementation of prior art devices.
In real-time signal processing applications, especially in speech and image communications and radar/sonar signal processing, input data arrives serially. In prior art fast Fourier transforms (FFT) based algorithms, serial data is buffered and then transformed using FFT scheme of complexity O(N log N), where is O is the order of complexity and N is the transform size. Buffering the data requires O(N) time. In the prior art, "fast" algorithm based architectures required O(log N) time using O(N log N) hardware. This increases complexity of the processor, reduces effectiveness of VLSI design implementation and slows down overall transform speed.
In recent years visualized communications have become an expanding market, due to recent advances of video/image data compression and maturity of very large scale integrated (VLSI) technology. Digital processing of video signals has come of age and their applications related to video signal processing such as video phone, high definition television (HDTV), video conferencing, and multimedia are of great interest.
In the field of digital video and its applications, various groups have been working on standardizing and simplifying the art. Many options have been proposed by the Joint Photographic Experts Group (JPEG)), the International Telegraph and Telephone Consultative Committee (CCITT), and the Moving Picture Experts Group (MPEG). None of the techniques proposed performed as well as the market needs.